// 在未排序的数组中找到第 k 个最大的元素。
// 请注意，你需要找的是数组排序后的第 k 个最大的元素。
// 要求算法的时间复杂度小于Onlog。

// 暴露接口
function findKthLargest(nums: number[], k: number): number {
    let resIndex = nums.length - k;// 求出最终有序的结果索引
    let basis: number = -1;// 初始化轴点索引
    let left: number = 0;// 声明左指针
    let right: number = nums.length - 1;// 声明右指针
    // 根据快速选择返回的轴点位置确定快速选择算法的区间
    while (basis !== resIndex) {
        basis = partition(nums, left, right);// 返回轴点位置
        if (basis > resIndex) {// 轴点位置大于结果索引，选择左区间
            right = basis - 1;
        } else if (basis < resIndex) {// 轴点位置大于结果索引，选择右区间
            left = basis + 1;
        }
    }
    return nums[resIndex];
};
// 交换函数
function swap(nums: number[], index1: number, index2: number) {
    let temp = nums[index2];
    nums[index2] = nums[index1];
    nums[index1] = temp;
}
// 快速选择函数
function partition(nums: number[], leftP: number, rightP: number): number {
    swap(nums, leftP, Math.floor(Math.random() * (rightP - leftP + 1) + leftP));// 随机交换，防止算法退化
    let pivot: number = nums[leftP];// 轴点元素
    let lastLow: number = leftP;// 小于等于轴点区间的尾指针
    // curr指针指向无序区间元素
    for (let curr = leftP + 1; curr <= rightP; curr++) {
        if (nums[curr] <= pivot) {// 交换无序区间元素与小于等于区间元素
            swap(nums, curr, lastLow + 1);
            lastLow++;
        }
    }
    swap(nums, leftP, lastLow);// 轴点归位
    return lastLow;
}

// 这道题在数据结构算法问题中属于典型的TopK问题
// TopK问题最典型的解法就是使用快速排序的前身---> 快速选择算法
// 我们把快速排序算法拆开来看，递归深度中的每一轮次，需要通过快速选择算法确定一个轴点位置
// 轴点位置就是指该位置是数组排序后元素所在的正确位置（详细讲解可查阅清华大学数据结构课程）
// 这道题目需要找到有序数组TopK的位置，那么我们一开始就可以知道k对应的最终索引的数值
// 我们使用快速选择算法求出轴点位置，然后用轴点位置与最终索引位置进行比较
// 根据轴点索引的大小关系就可以判断需要对数组的左右哪个部分作快速选择
// 而快速选择算法的内部实现可以照搬快速排序
// 首先为了防止极端情况算法的退化，先随机选择一个轴点，然后确定一个指针lastlow
// lastlow指针指向轴点小于等于区间的最后一个元素
// 然后我们遍历这个快速选择区间，不断地缩小无序区间，扩大小于等于轴点区间与大于轴点区间
// 最终使用lastlow指针交换即可得到正确的轴点位置索引
// 然后就可以返回主函数循环体下进行判断求解。
// 简单来说TopK问题的通解法可以理解为是一个不需要实现递归划分的快速排序算法，
// 用来复习快速排序的核心是蛮好的一个例题；同样道理的还有例如消除、统计逆序对问题中的简易归并排序算法过程。